home *** CD-ROM | disk | FTP | other *** search
-
- /*---------------------------------------------------------------------*\
- | |
- | CPP -- a stand-alone C preprocessor |
- | Copyright (c) 1993 Hacker Ltd. Author: Scott Bigham |
- | |
- | Permission is granted to anyone to use this software for any purpose |
- | on any computer system, and to redistribute it freely, with the |
- | following restrictions: |
- | - No charge may be made other than reasonable charges for repro- |
- | duction. |
- | - Modified versions must be clearly marked as such. |
- | - The author is not responsible for any harmful consequences of |
- | using this software, even if they result from defects therein. |
- | |
- | hash.c -- maintain hash table for macro lookup |
- \*---------------------------------------------------------------------*/
-
- #include <stdlib.h>
- #include <string.h>
- #include "global.h"
- #include "ztype.h"
- #include "alloc.h"
-
- #define hash_key(h) \
- (((h)->flags & INLINE_KEY) ? (h)->_id.inline : (h)->_id.out_of_line)
-
- #define HASH_SIZE 1009
-
- extern char *magic_words[];
- extern int N_MWORDS, N_M2WORDS;
-
- static Hash *H[HASH_SIZE];
-
- /*
- hash_id() -- compute a hash value for the identifier pointed to by |s|;
- place a pointer to the first character after the identifier in |*end|.
-
- Credit where it's due -- this hash function was originally suggested by Chris
- Torek on comp.lang.c. As an explanation of the implementation, he
- offered: "What *does* that 33 do? I have no idea."
- */
- unsigned int hash_id(s, end)
- register char *s;
- char **end;
- {
- register unsigned int h = 0;
-
- for (; is_ctok(*s); s++)
- /* h = h * 33 + *s; */
- h += (h << 5) + *s;
- if (end)
- *end = s;
- return h % HASH_SIZE;
- }
-
- /* set_key() -- set the key text of hash item |h| to |s| */
- static void set_key(h, s)
- register Hash *h;
- register char *s;
- {
- if (strlen(s) <= 7) {
- h->flags |= INLINE_KEY;
- (void)strcpy(h->_id.inline, s);
- } else {
- h->flags &= ~INLINE_KEY;
- h->_id.out_of_line = strdup(s);
- }
- }
-
- /* release_key() -- release the memory associated with the key for hash
- item |h| */
- static void release_key(h)
- register Hash *h;
- {
- if (!(h->flags & INLINE_KEY))
- free(h->_id.out_of_line);
- h->flags |= INLINE_KEY;
- h->_id.inline[0] = '\0';
- }
-
- /*
- hash_add() -- add to the hash table an entry for the identifier |s|, with
- hash value |hv| and macro value |M|
- */
- void hash_add(s, hv, M)
- char *s;
- unsigned int hv;
- Macro *M;
- {
- register Hash *h = alloc_Hash();
-
- h->data = M;
- h->next = NULL;
- set_key(h, s);
- h->next = H[hv];
- H[hv] = h;
- }
-
- /*
- hash_unlink() -- destroy the hash object pointed to by |h|; return a
- pointer to the hash object following |h|. Used in hash_remove().
- */
- static Hash *hash_unlink(h)
- register Hash *h;
- {
- register Hash *hh = h->next;
-
- release_key(h);
- free_Macro(h->data);
- dealloc_Hash(h);
- return hh;
- }
-
- /*
- hash_remove() -- remove the hash object for identifier |s|, with hash
- value |hv|
- */
- void hash_remove(s, hv)
- char *s;
- unsigned int hv;
- {
- register Hash *h;
-
- if (!H[hv])
- return;
- if (streq(hash_key(H[hv]), s)) {
- H[hv] = hash_unlink(H[hv]);
- return;
- }
- for (h = H[hv]; h->next; h = h->next)
- if (streq(hash_key(h->next), s)) {
- h->next = hash_unlink(h->next);
- return;
- }
- }
-
- /*
- magic_check() -- determine if the conditionally-active magic preprocessor
- constant in hash object |h| is in fact active
- */
- static int magic_check(h)
- register Hash *h;
- {
- if (ansi && streq(hash_key(h), "__STDC__"))
- return 1;
- if ((get_mode() & IF_EXPR) && streq(hash_key(h), "defined"))
- return 1;
- if (fluff_mode && streq(hash_key(h), "__FLUFF__"))
- return 1;
- return 0;
- }
-
- /*
- lookup() -- look for the identifier |s| with hash value |hv| in the hash
- table. Return its associated macro value, or NULL if the identifier is
- not present
- */
- Macro *lookup(s, hv)
- register char *s;
- unsigned int hv;
- {
- register Hash *h;
-
- for (h = H[hv]; h; h = h->next)
- if (streq(hash_key(h), s)) {
- if (!(h->data->flags & MAGIC2) || magic_check(h)) {
- return h->data;
- } else {
- return NULL;
- }
- }
- return NULL;
- }
-
- /*
- hash_setup() -- initialize the hash table and add the predefined tokens
- */
- void hash_setup()
- {
- register int i;
- register Macro *M;
- unsigned int hv;
-
- #if 0
- for (i = 0; i < HASH_SIZE; i++)
- H[i] = NULL;
- #endif
- for (i = 0; i < N_MWORDS; i++) {
- M = mk_Macro();
- M->flags = MAGIC;
- if (i < N_M2WORDS)
- M->flags |= MAGIC2;
- hash_add(magic_words[i], hash_id(magic_words[i], NULL), M);
- }
- }
-
- /*
- hash_clean_undef() -- remove all identifiers that were #undef'ined via -U
- from the hash table
- */
- void hash_clean_undef()
- {
- register int i;
- register Hash *h;
-
- for (i = 0; i < HASH_SIZE; i++) {
- while (H[i] && H[i]->data->flags & UNDEF)
- H[i] = hash_unlink(H[i]);
- if (H[i]) {
- for (h = H[i]; h->next; h = h->next)
- if (h->next->data->flags & UNDEF)
- h->next = hash_unlink(h->next);
- }
- }
- }
-
- /* hash_free() -- deallocate all hash objects */
- void hash_free()
- {
- #ifdef DEBUG /* explicitly clean up, to check for memory leaks */
- int i;
- Hash *h;
-
- for (i = 0; i < HASH_SIZE; i++)
- for (h = H[i]; h; h = hash_unlink(h))
- continue;
- cleanup_Hash();
- cleanup_Macro();
- #endif
- }
-